Problem statement: zenit13kkg

Možno si spomínate na Luciu a jej problém so štekajúcimi psami zo školského kola. Potom, ako jej Maroško poradil kúpiť si štuple do uší prišla s novým problémom. Tento problém sa týka nielen dediny Baranovce, ale celého okolia.

Baranovce sa nachádzajú v rovinatom regióne Slovenska a v ich blízkom okolí je ešte niekoľko iných dedín. Lucia stojí na čele skupiny aktivistov, ktorí by chceli docieliť, aby medzi týmito obcami vznikla kvalitná a hustá sieť cyklotrás. Maroško Lucii sľúbil, že projekt zabezpečí od návrhu až do finálnej realizácie. Prvou úlohou je premyslieť, kade cyklotrasy povedú.

Na prvom riadku vstupu sú celé čísla R a S - rozmery mapy. Na ďalších R riadkoch je samotná mapa. Tá pozostáva z bodiek a znakov X, ktoré označujú pozície dedín. Môžete predpokladať, že R a S sú aspoň 3 a nepresahujú 100. Predpokladajte tiež, že dedín je medzi 2 a 30 vrátane a že sa nedotýkajú hranou ani rohom.

Na výstup vypíšte mapu s cyklotrasami. Rozmery mapy a pozície dedín musia byť zachované. Niektoré bodky nahraďte znakmi #, ktoré označujú cyklotrasy.

Z políčka s cyklotrasou sa vieme dostať na iné políčko s cyklotrasou len ak zdieľajú hranu (každé políčko ma teda najviac štyroch susedov). Pre cyklosieť musí platiť, že z každej dediny do každej vieme prejsť len po cylkotrasových políčkach. Aby cyklisti v dedinách nezavadzali kravičkám a iným účastníkom cestnej premávky, musíte sieť navrhnúť tak, aby sme dediny dokázali obísť. V príklade nižšie je ľavá sieť nevhodná, kým pravá je vďaka obchádzke strednej dediny vhodná.

......... .........
......... ...###...
.X##X##X. .X##X##X.
......... .........

Okrem týchto podmienok musí platiť, že políčok s cyklotrasami nesmie byť na výstupe viac ako 3500. Spomedzi všetkých vyhovujúcich riešení vypíšte ľubovoľné (nemusí platiť, že počet políčok # je minimálny). Z podmienok v zadaní vyplýva, že bude existovať aspoň jedno riešenie.

Poznámka: Pôvodná rozprávka bola o pánovi Steinerovi, ktorý pestuje v záhrade stromy. Potom sme sa ale rozhodli, že rozprávka s Luciou bude vhodnejšia. O pánovi Steinerovi sa teda možno dočítate až na celoštátnom kole.

5 5
X....
...X.
.....
.....
.X... 

X#...
.##X.
.#...
.#...
.X...

5 10
..........
.X..X..X.X
..........
.X.X.X...X
.......X.. 

..........
.X..X..X.X
.#########
.X.X.X.#.X
.......X.. 

6 6
......
.X....
....X.
......
......
...... 

#.#.##
.X...#
.#..X#
##...#
#....#
######